A file system is an organized collection of computer files, stored in a computer readable storage medium, such as a hard disk, a floppy disk, or a magnetic tape. The fundamental unit of storage for a file system is a block, usually of a fixed size, and files are stored in one or more blocks. Blocks may either be allocated or free. Allocated blocks are those blocks which are currently being used to store a file or a part of file, if the file is larger than the block size. Free blocks are not in use and are available for storing a new file. The collection of all the free blocks in a file system is termed the free space.
For example, with reference to FIG. 1, file system 1A consists of fifteen blocks, labelled 1-15. Blocks 2 and 3 are allocated to file A, blocks 6-10 are allocated to file B, and blocks 11-13 are allocated to file C. The free space of file system 1A comprises blocks 1, 4-5, and 14-15, for a total of five blocks. File system 1G also comprises three files of two, five, and three blocks in size, and five free blocks, but its free space comprises a different set of blocks, blocks 11-15.
Contiguous blocks are those blocks which are found next to each other in the storage medium. Due to the physical properties of the storage device, data from contiguous blocks may be read faster than from non-contiguous blocks. As a result, contiguous blocks are highly valued in a file system, because performance is optimized if a file is stored in contiguous blocks. In the example, file B stored in file system 1A comprises five contiguous blocks, located at blocks 6-10. The largest contiguous free space in file system 1A is two blocks, one of which is found at blocks 4-5. On the other hand, the largest contiguous free space in file system 1G is five blocks, located at blocks 11-15.
In order to store a file in contiguous blocks, a sufficient number of contiguous free blocks in the free space must be found. However, over the course of creating and deleting files it is common for the free space to become fragmented. A fragmented free space is one in which the free blocks are not in a large contiguous section but spread out into much smaller sections throughout the file system. In FIG. 1, the free space of file system 1A is fragmented into three fragments at blocks 1, 4-5, and 14-15. On the other hand, the free space in file system 1G is not fragmented but contiguous. Therefore, it is possible that there is an insufficient number of contiguous free blocks to store a file, even though the total number of free blocks is more than enough to store the file. In the example, both file systems 1A and 1G have five free blocks of storage, but only file system 1G can contiguously store a four-block file.
One conventional response to the problem of free space fragmentation is to "squeeze" the file system. During a squeeze operation, all the files are shifted over the beginning or to the end of the file system. For example, file A of file system 1A is shifted block-by-block from blocks 2-3 to blocks 1-2. During the shift, the first block of file A at block 2 is copied to block 1 (see file system 1B), and block 2 is freed (see 1C), leaving file A temporarily fragmented. Next, the second block is copied from block 3 to block 2 (see 1D), and block 3 is freed, resulting in file system 1E. After file A was shifted, file B is shifted by a similar procedure from blocks 6-10 to blocks 3-7 (see 1F), and file C from blocks 11-13 to blocks 8-10 (see 1G). These movements result in a contiguous free space comprising blocks 11-15 for five blocks and enough room to contiguously store file D at blocks 11-14 (see 1H).
Squeezing a file system requires shifting every file located after the first unallocated block in the file system. In this example, a total of ten blocks were shifted to produce file system 1G from file system 1A. This process may take quite some time to complete, and the user who wishes to store a file must wait for the free space to be defragmented.
As a result, a more common conventional response to the fragmentation of free space is to allow the file system to store files in non-contiguous blocks. Thus, in FIG. 2 a four-block file D is stored within file system 2A in three non-contiguous fragments at blocks 1, 4-5, and 14. File systems which allow files to be stored in non-contiguous blocks or "fragmented" are called non-contiguous file systems. Although non-contiguous file systems allow all the available blocks to be allocated in storing files and enable a file to be stored immediately, reading a fragmented file is slower than reading a contiguous file. For example, reading file D of file system 2A involves reading block 1, skipping to block 4, reading blocks 4 and 5, skipping to block 14, and finally reading block 14. There is a performance penalty every time a block is skipped.
A video system server, which is a file system dedicated to storing and playing back video files, however, imposes a set of constraints which make either conventional solution, squeezing the file system or allowing fragmented files, disadvantageous. In playing back a video file, the amount of time involved in reading the video file from the file system is so important that the video file must be stored contiguously. Therefore, the performance penalty of the fragmented file approach is simply unacceptable for use in high-performance video system servers. As a result, a video system server requires that every file be contiguously stored.
The squeeze defragmentation solution, on the other hand, is also disadvantageous. Recall that during the shift operation of a file, the file is temporarily fragmented (compare file system 1C). This fact means that the video file is unavailable for play back during the shift operation. Moreover, if the file is being played back during the squeeze defragmentation, the procedure must wait for the play back to complete. Therefore, squeezing a file system requires that the file system be taken off-line during the defragmentation. As a result, an on-line video system server requires that every file continues to be contiguously stored, even during a defragmentation, so that every video file may be played back.
In addition, video files are typically very large, about two gigabytes, but squeezing a file system moves many files, a very time-consuming task further exasperating the problem of the video server being off-line. Therefore, there is a need for on-line defragmentation of a high-performance, contiguous-file file system, such as a video system server.